package tree.binary;

import java.util.Stack;
import tree.Traversal;

/**
 * 堆遍历
 *
 * @Author: wangxiaonan
 * @Date: 2019/3/5
 **/
public class StackTraversal implements Traversal<BinaryTreeNode> {

    /**
     * ---------- 前序遍历 ----------
     * 841356972
     * ---------- 中序遍历 ----------
     * 134658729
     * ---------- 后序遍历 ----------
     * 316542798
     */
    public static void main(String[] args) {
        StackTraversal st = new StackTraversal();
        BinaryTreeNode root = BinaryTreeNode.initBinaryTree();
        System.out.println("\n---------- 前序遍历 ----------");
        st.preOrderTraversal(root);
        System.out.println("\n---------- 中序遍历 ----------");
        st.inOrderTraversal(root);
        System.out.println("\n---------- 后序遍历 ----------");
        st.postOrderTraversal(root);
        System.out.println();
    }

    private static void print(Object data) {
        System.out.print(data.toString());
    }

    @Override
    public void preOrderTraversal(BinaryTreeNode tree) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = tree;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                print(node.getData());
                stack.push(node);
                node = node.getLeft();
            } else {
                node = stack.pop();
                node = node.getRight();
            }
        }
    }

    @Override
    public void inOrderTraversal(BinaryTreeNode tree) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = tree;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                stack.push(node);
                node = node.getLeft();
            } else {
                node = stack.pop();
                print(node.getData());
                node = node.getRight();
            }
        }
    }

    @Override
    public void postOrderTraversal(BinaryTreeNode tree) {
        Stack<BinaryTreeNode> stack = new Stack<>();
        Stack<BinaryTreeNode> out = new Stack<>();
        BinaryTreeNode node = tree;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                stack.push(node);
                out.push(node);
                node = node.getRight();
            } else {
                node = stack.pop();
                node = node.getLeft();

            }
        }
        while (out.size() > 0) {
            print(out.pop().getData());
        }
    }
}
